package java学习.代码随想录.动态规划;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * **************
 * 项目名称: 蓝桥杯-Java学习 <br/>
 * 文件名称:  <br/>
 * 文件描述: 这里添加您的类文件描述，说明当前文件要包含的功能。 <br/>
 * 文件创建：刘世锦Lenovo <br/>
 * 创建时间: 2022/8/25 <br/>
 *
 * @version v1.0 <br/>
 * @update [序号][日期YYYY-MM-DD][更改人姓名][变更描述]<br/>
 * *************
 */
public class 单词拆分 {
    /**
     给定一个非空字符串 s 和一个包含非空单词的列表 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。
     说明：
     拆分时可以重复使用字典中的单词。
     你可以假设字典中没有重复的单词。
     示例 1： 输入: s = "leetcode", wordDict = ["leet", "code"] 输出: true 解释: 返回 true 因为 "leetcode" 可以被拆分成 "leet code"。
     示例 2： 输入: s = "applepenapple", wordDict = ["apple", "pen"] 输出: true 解释: 返回 true 因为 "applepenapple" 可以被拆分成 "apple pen apple"。
     注意你可以重复使用字典中的单词。
     示例 3： 输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"] 输出: false
     */

    /**
     * bagsize: s ，物品：wordDict 字典
     * 组合数：先物品、再背包
     * 1. dp[j] : 字典的单词 可以凑成 长度 为 0~j-1 的子串
     * 2. 如果 0~i-1 的子串为 true 且 i~j-1 的子串是字典的单词，则 0~j-1 =>dp[j] = true(可包含)
     * 3. dp[0] = 1. 因为是求组合数 不是排列数
     */
    public static boolean wordBreak(String s, List<String> wordDict) {
        boolean [] dp = new boolean[s.length()+1];
        dp[0] = true;

//  物品长度
            for (int i = 0; i < s.length(); i++) {
//          背包长度
                for (int j =i ; j <=s.length() ; j++) {
//          如果 0~i-1的串能被字典表示， 且 i~j-1 的子串 也能被字典表示，则 0~j-1就能被字典表示
                    if (dp[i] && wordDict.contains(s.substring(i,j))){
                        dp[j] = true;
                    }
//                        dp[j] = dp[j-item.charAt(i)];
                }
            }
        System.out.println(Arrays.toString(dp));
        return dp[s.length()];
    }
    public static boolean wordBreak1(String s, List<String> wordDict) {
        boolean[] dp = new boolean[s.length() + 1];
        dp[0] = true;
//        背包字符串长度
        for (int j = 1; j <= s.length(); j++) {
//       物品
            for (int i = 0; i < j; i++) {
                if (wordDict.contains(s.substring(i,j)) && dp[i]) {
                    dp[j] = true;
                }
            }
        }
        System.out.println(Arrays.toString(dp));
        return dp[s.length()];
    }

    public static void main(String[] args) {
        /**
         输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
         */
       String s = "l e e tc ode ";
//        String s = "applepenapple";
//        String s = "catsandog";
        List<String> wordDict = new ArrayList<String>() ;
        wordDict.add("leet");
        wordDict.add("code");

//        wordDict.add("apple");
//        wordDict.add("pen");

//        wordDict.add("cats");
//        wordDict.add("dog");
//        wordDict.add("sand");
//        wordDict.add("and");
//        wordDict.add("cat");

        System.out.println(wordBreak1(s,wordDict));
        System.out.println("------------");
        System.out.println(wordBreak(s,wordDict));

//        翻转字符串
        new StringBuffer(s).reverse();
//        去除字符串空格
        System.out.println(s.replaceAll(" ",""));
        System.out.println(s.replaceAll(" ","").length());
    }
}
